class Solution
{
public:
    int minAddToMakeValid(string s)
    {
        int leftCount = 0;
        int needInsert = 0;
        for (char c : s)
        {
            if (c == '(')
            {
                ++leftCount;
            }
            else
            {
                if (leftCount == 0)
                {
                    ++needInsert;
                }
                else
                {
                    --leftCount;
                }
            }
        }
        needInsert += leftCount;
        return needInsert;
    }
};